2661. Price labels

The company “Black Label” has received two orders for manufacturing supermarket price labels. Each order specifies the number of labels and the prices to be printed. Your task is to print all the unique prices for which labels will be manufactured after completing both orders. Each price should be printed only once.

Input. The first line contains the number n (n ≤ 10⁵) of price labels for the first supermarket. The second line contains a list of n prices to be printed for the first supermarket. The third line contains the number m (m ≤ 10⁵) of price labels for the second supermarket. The fourth line contains a list of m prices to be printed for the second supermarket. All numbers are integers and do not exceed 10⁹.

Output. Print the unique prices that will be printed on the labels, with each price appearing only once. The prices should be printed in ascending order.

Sample input

Sample output

100 25 300 400 12000

10 25 25 500

10 25 100 300 400 500 12000

SOLUTION

data structures – set

Algorithm analysis

In this problem, we must find the union of two sets. This can be accomplished using either a set or a binary tree. Insert the values from all price labels into the chosen data structure, ensuring that it does not contain duplicate elements. For example, when using a binary tree, you should insert a new number only if it is not already present. Finally, print all the elements in ascending order.

Algorithm implementation

The values of the manufactured price tags will be inserted into the set s.

set<int> s;

Read the input data. Insert n price tags from the first supermarket into the set s.

scanf("%d",&n);

for(i = 0; i < n; i++)

{

scanf("%d",&val);

s.insert(val);

}

Insert m price tags from the second supermarket into the set s.

scanf("%d",&m);

for(i = 0; i < m; i++)

{

scanf("%d",&val);

s.insert(val);

}

Print the contents of the set s.

for (int x : s)

printf("%d ", x);

printf("\n");

Algorithm implementation – binary tree

The tree should contain only unique elements (a set of supermarket price tags). We’ll insert a new number into the tree only if it is not already present.

#include <stdio.h>

class TreeNode

{

public:

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Tree

{

public:

TreeNode *head;

Tree() : head(NULL) {};

void Insert(int val)

{

Insert(head, val);

}

void Insert(TreeNode *&tree, int val)

{

if (tree == NULL)

{

tree = new TreeNode(val);

return;

}

if (val == tree->val) return;

if (val < tree->val)

Insert(tree->left, val);

else

Insert(tree->right, val);

}

void InOrder(void)

{

InOrder(head);

}

void InOrder(TreeNode *tree)

{

if (tree == NULL) return;

InOrder(tree->left);

printf("%d ", tree->val);

InOrder(tree->right);

}

};

int n, val;

int main(void)

{

Tree *resTree = new Tree();

scanf("%d", &n);

while (n--)

{

scanf("%d", &val);

resTree->Insert(val);

}

scanf("%d", &n);

while (n--)

{

scanf("%d", &val);

resTree->Insert(val);

}

resTree->InOrder();

printf("\n");

return 0;

}

Java implementation

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

TreeSet<Integer> s = new TreeSet<Integer>();

int n = con.nextInt();

while(n-- > 0)

{

int val = con.nextInt();

s.add(val);

}

n = con.nextInt();

while(n-- > 0)

{

int val = con.nextInt();

s.add(val);

}

// Iterator iter = s.iterator();

// for(int i = 0; i < s.size(); i++)

// System.out.print(iter.next() + " ");

for(int i : s)

System.out.print(i + " ");

con.close();

}

Java implementation – binary tree

import java.util.Scanner;

class TreeNode

{

int val;

TreeNode left;

TreeNode right;

TreeNode(int x)

{

val = x;

left = null;

right = null;

}

class Tree

{

TreeNode head;

Tree()

{

head = null;

}

void Insert(int val)

{

head = Insert(head, val);

}

// objects are passed by copy

TreeNode Insert(TreeNode tree, int val)

{

if (tree == null)

{

return new TreeNode(val);

}

if (val == tree.val) return tree;

if (val < tree.val)

tree.left = Insert(tree.left, val);

else

tree.right = Insert(tree.right, val);

return tree;

}

void InOrder()

{

InOrder(head);

}

void InOrder(TreeNode tree)

{

if (tree == null) return;

InOrder(tree.left);

System.out.print(tree.val + " ");

InOrder(tree.right);

}

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

Tree resTree = new Tree();

int n = con.nextInt();

for(int i = 0; i < n; i++)

{

int x = con.nextInt();

resTree.Insert(x);

}

n = con.nextInt();

for(int i = 0; i < n; i++)

{

int x = con.nextInt();

resTree.Insert(x);

}

resTree.InOrder();

System.out.println("");

con.close();

}

Python implementation

Read the price lists from the first and second supermarkets.

n = int(input())

lst1 = list(map(int,input().split()))

m = int(input())

lst2 = list(map(int,input().split()))

Convert the lists lst1 and lst2 into sets and perform a union operation on them (“or”). As a result, the list res will contain unique prices from both supermarkets in arbitrary order.

res = list(set(lst1) | set(lst2))

Print the prices in ascending order.

print(*sorted(res))

Python implementation

The values of the manufactured price tags will be inserted into the set s.

s = set()

Read n price tags for the first supermarket and add them to the set s.

n = int(input())

lst1 = list(map(int,input().split()))

for x in lst1:

s.add(x)

Read m price tags for the second supermarket and add them to the set s.

m = int(input())

lst2 = list(map(int,input().split()))

for x in lst2:

s.add(x)

Print the contents of the set s in ascending order. Since sets in Python do not guarantee element order, use the sorted() function to ensure the elements are printed in ascending order.

for x in sorted(s):

print(x, end=' ')

print()